package leetcode_core.leetcode_1;

public class SuperPow {
    public static int MOD = 1337;
    public int superPow(int a, int[] b) {
        return superPow(a,b,b.length-1);
    }

    private int superPow(int a,int[] b,int index){
        //递归的base-case
        if(index == -1){
            return 1;
        }
        //取出最后一个数
        int last = b[index];
        //将原问题化简,缩小规模求解
        int part1 = myPow(a,last);
        int part2 = myPow(superPow(a,b,index-1),10);
        return (part1%MOD)*(part2%MOD)%MOD;//凡是可能存在溢出的地方都应该进行取模
    }

    private int myPow(int a,int k){
        if(k==0){
            return 1;
        }
        if(k%2 == 1){//k是奇数
            return ((a%MOD) * (myPow(a,k-1)%MOD)%MOD);
        }else{
            //k是偶数
            int sub = myPow(a,k/2);
            return  (sub%MOD) * (sub%MOD) %MOD;
        }
    }

}
